P2P 与路由专栏导览
标签
分布式/P2P 与路由
字数
954 字
阅读时间
4 分钟
本专栏收录结构化覆盖网（structured overlay）与分布式哈希表（DHT） —— 在一个没有中心目录、节点随时上下线、规模到几十万甚至上百万的自治系统里，怎么让任何一个节点都能找到某个 key 该由谁负责。
这四篇都写在 2001 到 2002 年之间，共同的出发点是被 一致性哈希 打开的那个思路：把 key 和节点都映射到同一个逻辑空间里，让"找 key"退化成"在空间里朝目标走"，于是不需要任何目录服务器。四篇的分歧在于这个逻辑空间长什么样、每个节点要为此记住多少东西。
| 篇 | 空间 | 路由方式 | 每节点状态 |
|---|---|---|---|
| 01 · CAN | 朝目的坐标贪心转发 | ||
| 04 · Kademlia | 一圈标识符 + XOR 度量 | 路由表按位逐级覆盖 |
一个反复出现的设计张力值得先记下来：
目录
- 01 · CAN —— 唯一不靠环的一条路：把哈希桶摊进
维坐标空间，邻居判据是维度相接 - 02 · Chord —— 标识符环与 finger table，把每节点邻居数压到
- 03 · Pastry —— 第一个正面处理“逻辑跳与物理跳不一致”，用三层结构做 route locality
- 04 · Kademlia —— 把距离换成 XOR，路由表的结构、查找的并行与节点可信度都由这一个选择推出
阅读顺序
01 → 02 → 03 → 04。
01 走的是几何这条路（坐标空间里的直线），02 到 04 走的是标识符前缀/位这条路（环上的逐段或逐位逼近）。先读 01 的好处是它的对照最刺眼：它放弃了
后面的三篇内部是逐层收拢的关系：02 是这条线的基础形态（finger table），03 在它之上加了前缀匹配与叶集、并第一次正经处理"逻辑跳与物理跳不一致"；04 把度量换成 XOR，于是路由表的结构、查找的并行性、以及"节点长时间在线更可信"这件事都能从这一个选择里推出来。
相关
这一专栏的结论在今天主要下沉成了中间件里的分片与路由层，而不再体现为新的 P2P 覆盖网：
- 一致性哈希算法 是本专栏的前置 —— 它把"哈希环"这个工具交出来，02 到 04 都是在这个工具上做工程化；
- Ceph 的 CRUSH 与 01 的坐标空间是两条都能"算出位置"的路线，但 CAN 要靠节点之间维持几何邻居关系，CRUSH 是纯函数、节点间不需要邻居表；
- Dynamo 与 Cassandra 则是把一致性哈希直接当作生产系统的分区手段（前者配虚拟节点，后者改成保序哈希 + 移 token）。
YJ